#include <vector>
#include <iostream>

using namespace std;

class Solution {
private:
    int result = 0;
public:
    int trap(vector<int>& height) {
        int length = height.size();
        if(length == 0)
            return 0;
        
        vector<int> leftmax(length, 0);
        vector<int> rightmax(length, 0);

        leftmax[0] = height[0];
        for(int i = 1; i < length; i++){
            leftmax[i] = max(leftmax[i-1], height[i]);
        }

        rightmax[length-1] = height[length-1];
        for(int i = length - 2; i >= 0; i--){
            rightmax[i] = max(rightmax[i+1], height[i]);
        }

        for(int i = 1; i < length-1; i++){
            result += (min(rightmax[i], leftmax[i]) - height[i]);
        }

        return result;
    }
};